package bu.met.cs664.cox;

import java.util.ArrayList;
import java.util.List;

/**
 * Minimax algorithm for Mancala with a branching factor of six.
 *
 * @author mcox
 */
public class MiniMax {

    /** The number of choices at each node */
    private static final int BRANCHING_FACTOR = 6;

    /** Construct a new minimax tree and calculate the best move for the current player based on tree depth  */
    public static int calculateNextMove(Board board, Board.Player player, Board.Player opponent, int depth) {
        Node root = new Node(Node.NodeType.MAXIMIZER, new Board(board), null);
        root.buildTree(player, opponent, depth);
        root.calculateValue(player);
        return root.chosenChild;
    }

    /** A node in the minimax tree. */
    private static class Node {

        /** Type of node */
        private static enum NodeType {
            NULL, MAXIMIZER, MINIMIZER;

            public static NodeType complement(NodeType nodeType) {
                if (nodeType == MAXIMIZER) {
                    return MINIMIZER;
                }

                return MAXIMIZER;
            }
        }

        /** What type of node is this */
        public NodeType type;

        /** The board for this node */
        public Board board;

        /** The result of the turn this node represents */
        public Board.TurnResult turnResult;

        /** The value of this node after calculating for min or max */
        public int value;

        /** The chosen child that derived the value */
        public int chosenChild;

        /** The children move choices */
        public List<Node> children = new ArrayList<>();

        /** Construct a new node with the board and turn result taken on visiting this node */
        public Node(NodeType type, Board board, Board.TurnResult turnResult) {
            this.type = type;
            this.board = board;
            this.turnResult = turnResult;
        }

        /**
         * build a new tree of size b^d. Nodes are added in level order with each level alternating between minimizer
         * and maximizer. Due to Mancala rules a player may take multiple turns in a row, in that case the same node
         * type is added for those children. Only adds nodes that end to valid moves and terminates when depth is
         * reached or a game path results in the game ending.
         */
        public void buildTree(Board.Player player, Board.Player opponent, int depth) {
            if (depth > 0) {
                for (int i = 0; i < BRANCHING_FACTOR; ++i) {
                    Board childBoard = new Board(board);
                    Board.TurnResult turnResult;

                    if (type == NodeType.MAXIMIZER) {
                        if (!childBoard.isValidMove(player, i)) {
                            turnResult = null;
                        } else {
                            turnResult = childBoard.takeTurn(player, i);
                        }
                    } else {
                        if (!childBoard.isValidMove(opponent, i)) {
                            turnResult = null;
                        } else {
                            turnResult = childBoard.takeTurn(opponent, i);
                        }
                    }

                    Node child;
                    if (turnResult == null) {
                        child = new Node(NodeType.NULL, null, null);
                    } else if (turnResult.getState() == Board.BoardState.SAME_PLAYER) {
                        child = new Node(type, childBoard, turnResult);
                    } else {
                        child = new Node(NodeType.complement(type), childBoard, turnResult);
                    }
                    children.add(child);
                }

                for (Node childNode : children) {
                    if (childNode.type != NodeType.NULL && !childNode.turnResult.isGameOver()) {
                        childNode.buildTree(player, opponent, depth - 1);
                    }
                }
            }
        }

        /**
         * Calculate the value of this node. If a leaf then it's a Maximizer and returns the store value for that
         * player. Otherwise solicit values from children and based on disposition choose a min or max value.
         */
        public int calculateValue(Board.Player player) {
            if (children.isEmpty()) {
                return board.getPlayerStoreCount(player);
            } else {
                int min = Integer.MAX_VALUE;
                int minChild = 0;
                int max = Integer.MIN_VALUE;
                int maxChild = 0;

                int childIndex = 0;
                for (Node child : children) {
                    if (child.type != NodeType.NULL) {
                        int childValue = child.calculateValue(player);

                        if (childValue < min) {
                            min = childValue;
                            minChild = childIndex;
                        }

                        if (childValue > max) {
                            max = childValue;
                            maxChild = childIndex;
                        }
                    }

                    ++childIndex;
                }

                if (type == NodeType.MAXIMIZER) {
                    value =  max;
                    chosenChild = maxChild;
                } else {
                    value = min;
                    chosenChild = minChild;
                }

                return value;
            }
        }
    }
}
